package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class LeetCodeMain114 {
    public int[] constructArr1(int[] a) {
        if (a==null||a.length==0){
            return new int[0];
        }
        int length=a.length;
        int[] left=new int[length];
        int[] right=new int[length];
        Arrays.fill(left,1);
        Arrays.fill(right,1);
        for (int i = length-2; i >=0 ; i--) {
            left[i]=left[i+1]*a[i+1];
        }
        for (int i = 1; i < length; i++) {
            right[i]=right[i-1]*a[i-1];
        }
        for (int i = 0; i < length; i++) {
            left[i]*=right[i];
        }
        return left;
    }
    public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();
        Node cur=head;
        while (cur!=null){
            map.put(cur,new Node(cur.val));
            cur=cur.next;
        }
        Node n1=new Node(-1);
        Node n2=n1;
        cur=head;
        while (cur!=null){
            n2.next=map.get(cur);
            n2=n2.next;
            n2.random=map.get(cur.random);
            cur=cur.next;
        }
        n2.next=null;
        return n1.next;
    }
}
